There is a growing movement, driven by both industry and academia, towards a new network control paradigm called Software-Defined Networking (SDN). A logical (virtual) network that is implemented for a tenant of a hosting system is a good example for a software-defined network. Such a logical network connects a set of tenant's virtual machines that execute on one or more host machines, to each other and to other logical and/or physical networks. One of the challenges in today's SDN systems is adding physical workloads (e.g., one or more physical machines) to logical networks and applying the same logical network rules and policies to the physical workloads. For example, firewall rules can be applied to the virtual machines of a logical network in a distributed manner (e.g., through a security agent). Unlike software switches, a stateful firewall mechanism cannot be efficiently employed by a hardware switch. This is because, hardware switches are stateless and as such network data flows cannot be easily managed on them (i.e., keeping the state of every data flow requires a large amount of cache memory on the hardware switch which could be costly).